<!DOCTYPE html>
<html lang="en">
	<head>
		<meta charset="UTF-8">
		<meta http-equiv="X-UA-Compatible" content="IE=edge">
		<meta name="viewport" content="width=device-width, initial-scale=1.0">
		<title>Document</title>
	</head>
	<body>
		<script>
			/* 栈结构的封装 */
			class Stack {
				constructor() {
					this.items = []
				}

				pop() {
					return this.items.pop()
				}
				push(element) {
					return this.items.push(element)
				}
				toString() {
					var str = ''
					for (var i = this.items.length - 1; i >= 0; i--) {
						str += this.items[i]
					}
					return str
				}
				peek() {
					return this.items[this.items.length - 1]
				}
			}
			/* 利用栈将十进制转为二进制 */
			function decimalToBinary(decimal) {
				var binaryStack = new Stack()
				while (decimal > 0) {
					binaryStack.push(decimal % 2)
					decimal = Math.floor(decimal / 2)
				}

				return binaryStack.toString()
			}

			console.log('二进制', decimalToBinary(10))
			console.log('二进制', decimalToBinary(100))

			/* 队列:先进先出 */
			class Queue {
				constructor(arr) {
					this.items = arr || []
				}
				enqueue(element) {
					return this.items.push(element)
				}
				dequeue() {
					return this.items.shift()
				}
				isEmpty() {
					return this.items.length === 0
				}
			}

			/* 击鼓传花: 留下数字对应的那个人*/
			function passGame(gamerList, number) {
				if (!Array.isArray(gamerList)) throw new TypeError('GamerList must be Array!')
				var queue = new Queue(gamerList)
				var target
				while (!queue.isEmpty()) {
					for (var i = 0; i < number; i++) {
						queue.enqueue(queue.dequeue())
					}
					target = queue.dequeue()
				}
				return target
			}

			console.log('击鼓传花', passGame(['关羽', '张飞', '赵云'], 2))

			/* 优先级队列 */
			class PriorityQueue extends Queue {
				constructor(arr) {
					super(arr)
				}
				/* 模拟内部类 */
				QueueElement = class QueueElement {
					constructor(element, prioirity) {
						this.element = element
						this.prioirity = prioirity
					}
				}
				/* 重写了队列的入队列方法 */
				enqueue(element, prioirity) {
					// 使用内部类封装加入队列的方法
					var queueEle = new this.QueueElement(element, prioirity)
					if (this.items.length === 0) {
						this.items.push(queueEle)
					} else {
						for (var i = 0; i < this.items.length; i++) {
							if (queueEle.prioirity < this.items[i].prioirity) {
								this.items.splice(i, 0, queueEle)
								break
							}

							/* 如果到最后一轮循环还没添加, 则手动添加 */
							if (i === this.items.length - 1) {
								this.items.push(queueEle)
							}
						}
					}
				}
			}

			var prioirityQueue = new PriorityQueue()
			prioirityQueue.enqueue('张飞', 2)
			prioirityQueue.enqueue('刘备', 0)
			prioirityQueue.enqueue('关羽', 1)
			console.log('优先级队列', prioirityQueue)

			/* 单向链表 */
			class LinkedList {
				constructor() {
					this.head = null
					this.length = 0
				}
				Node = class Node {
					constructor(element) {
						this.next = null
						this.element = element
					}
				}
				append(element) {
					var node = new this.Node(element)
					if (this.length === 0) {
						this.head = node
					} else {
						var currentNode = this.head
						while (currentNode.next) {
							currentNode = currentNode.next
						}
						currentNode.next = node
					}
					this.length += 1
				}
				get(position) {
					if (position < 0 || position > this.length) throw new TypeError('The index overstep the boundary!')
					var currentNode = this.head
					var preNode = null
					var index = 0
					while (index++ < position) {
						preNode = currentNode
						currentNode = currentNode.next
					}
					return {
						preNode,
						currentNode
					}
				}
				insert(element, position) {
					if (position < 0 || position > this.length) {
						throw new TypeError('The index overstep the boundary!')
					}
					var node = new this.Node(element)
					if (this.length === 0) {
						return this.append(element)
					} else {
						var nodes = this.get(position)
						nodes.preNode.next = node
						node.next = nodes.currentNode
					}
				}
			}


			class DoublyLinkedList {
				constructor() {
					this.head = null
					this.tail = null
					this.length = 0
				}

				Node = class Node {
					constructor(element) {
						this.next = null
						this.prev = null
						this.element = element
					}
				}

				append(ele) {
					var node = new this.Node(ele)
					if (this.length === 0) {
						this.head = this.tail = node
					} else {
						node.prev = this.tail
						this.tail.next = node
						this.tail = node
					}

					this.length += 1
				}

				insert(position, ele) {
					if (position < 0 || position > this.length) {
						throw TypeError('The index overstep the boundary')
					}
					if (this.length === 0) {
						return this.append(ele)
					} else {
						var node = new this.Node(ele)
						if (position === 0) {
							node.next = this.head
							this.head.pre = node
							this.head = node
						} else if (position === this.length - 1) {
							node.pre = this.tail
							this.tail.next = node
							this.tail = node
						} else {
							var harfLength = this.length / 2
							var index
							var currentNode
							switch (true) {
								case position > harfLength:
									index = this.length - 1
									currentNode = this.tail
									while (index-- > position) {
										currentNode = currentNode.prev
									}
									break;
								case position <= harfLength:
									index = 0
									currentNode = this.head
									while (index++ < position) {
										currentNode = currentNode.next
									}
									break;
							}
							currentNode.prev.next = node
							currentNode.prev = node
							node.next = currentNode
							node.prev = currentNode.prev
						}
						this.length += 1
					}
				}

				indexOf(element) {
					var index = 0
					var currentNode = this.head
					while (currentNode) {
						if (currentNode.element === element) {
							return index
						}
						currentNode = currentNode.next
						index++
					}
					return -1
				}
			}

			var list = new DoublyLinkedList()
			list.append('张飞')
			list.append('刘备')
			list.append('关羽')
			list.insert(1, '赵云')
			console.log('双向链表', list)


			/* 二叉搜索树的封装 */

			/* 节点类 */
			class Node {
				constructor(key) {
					this.key = key
					this.left = null
					this.right = null
				}
			}

			/* 二叉搜索树 */
			class BinarySearchTree {
				constructor() {
					this.root = null
				}

				/* 插入节点的方法 */
				insert(key) {
					// 1. 新建节点
					const node = new Node(key)
					// 2. 添加到哪里去
					// 2-1: 根节点不存在直接放在根节点上
					if (!this.root) {
						return this.root = node
					}
					// 2-2: 根节点存在, 根据大小放置
					let currentNode = this.root
					let parent = null
					let isLeft = true
					while (currentNode) {
						// 父节点默认为当前节点
						parent = currentNode
						if (currentNode.key >= key) {
							// 节点小于当前节点
							currentNode = currentNode.left
							isLeft = true
						} else {
							// 节点大于当前节点
							currentNode = currentNode.right
							isLeft = false
						}
					}
					if (isLeft) {
						parent.left = node
					} else {
						parent.right = node
					}
				}

				/* 后序遍历 */
				/* 思路梳理 */
				/* 1. 遍历是干嘛的? 最终是让用户做操作, 所以需要传进一个handler */
				/* 2. 后序遍历是先root --> 左边 --> 右边. 所以先拿出root */
				prevorderTraversal(handler) {
					const process = (node) => {
						if (node) {
							handler(node) // 先处理根
							process(node.left)
							process(node.right)
						}
					}

					if (!this.root) throw new Error('二叉树为空')
					process(this.root)
				}
				midorderTraversal(handler) {
					if (!this.root) throw new Error('二叉树为空')
					const process = (node) => {
						if (node) {
							process(node.left)
							handler(node)
							process(node.right)
						}
					}
					process(this.root)
				}
				postorderTraversal(handler) {
					if (!this.root) throw new Error('二叉树为空')
					const process = (node) => {
						if (node) {
							process(node.left)
							process(node.right)
							handler(node)
						}
					}
					process(this.root)
				}

				/* 获取二叉树中最大的值 */
				max() {
					if (!this.root) throw new Error('二叉树为空')

					let currentNode = this.root,
						parent = null
					while (currentNode) {
						parent = currentNode
						currentNode = currentNode.right
					}

					return parent.key
				}
				min() {
					if (!this.root) throw new Error('二叉树为空')

					let currentNode = this.root,
						parent = null
					while (currentNode) {
						parent = currentNode
						currentNode = currentNode.left
					}

					return parent.key
				}

				/* 根据key查找是否存在该节点 */
				get(key) {
					// 情况一: 根节点不存在
					if (!this.root) return false
					// 情况二: root就是查找的节点
					if (this.root.key === key) return true

					// 情况三: root不是查找的节点
					// 2-1: 比root大
					// 2-2: 比root小
					let currentNode = this.root
					while (currentNode) {
						if (key > currentNode.key) {
							currentNode = currentNode.right
						} else if (key < currentNode.key) {
							currentNode = currentNode.left
						} else {
							return true
						}
					}
					// 代码能执行到这里, 意味着currentNode = null, 所以查无此节点,return false
					return false
				}

				/* 删除节点 */
				remove(key) {
					if (!this.root) throw new Error('二叉树为空')
					// 1. 找到删除节点
					let targetNode = null,
						isLeftNode = true,
						parentNode = null

					if (this.root.key === root) {
						targetNode = this.root
					}
					/* 不为根节点时 */
					else {
						let currentNode = this.root
						while (currentNode) {
							if (key > currentNode.key) {
								parentNode = currentNode
								isLeftNode = false
								currentNode = currentNode.right
							} else if (key < currentNode.key) {
								parentNode = currentNode
								isLeftNode = true
								currentNode = currentNode.left
							} else {
								targetNode = currentNode
							}
						}
					}
					/* 代码执行到这里, 如果targetNode没有值, 则意味着没有删除元素,删除失败,返回null */
					if (!targetNode) return null

					/* 再往下targetNode一定有值了 */
					/* 情况一: 删除的是叶子节点 */
					if (targetNode.left === null && targetNode.right === null) {
						if (isLeftNode) {
							parentNode.left = null
						} else {
							parentNode.right = null
						}
					}

					/* 情况二: 删除节点只有一个子节点 */
					/* 2-1: 只有右节点 */
					else if (targetNode.left === null) {
						if (isLeftNode) {
							parentNode.left = targetNode.right
						} else {
							parentNode.right = targetNode.right
						}
					}
					/* 2-2: 只有左节点 */
					else if (targetNode.right === null) {
						if (isLeftNode) {
							parentNode.left = targetNode.left
						} else {
							parentNode.right = targetNode.left
						}
					}
					/* 情况三: 删除的节点有两个子节点 */
					else {
						// 1. 寻找删除节点的前驱节点
						const successor = this.getSuccessor(targetNode)
						// 2. 处理删除节点的父节点
						if (this.root = targetNode) {
							this.root = successor
						} else if (isLeftNode) {
							parentNode.left = successor
						} else {
							parentNode.right = successor
						}

						// 3. 处理前驱节点的左右节点
						successor.left = targetNode.left
					}

				}

				/* 寻找后继节点 */
				getSuccessor(node) {
					let currentNode = node.right,
						successor = node,
						parentNode = null

					while (currentNode) {
						parentNode = successor
						successor = currentNode
						currentNode = currentNode.left
					}

					if (targetNode.right === successor) return

					parentNode.left = successor.right
					successor.right = targetNode.right
					return successor
				}
			}

			/* 红黑树 */
		</script>
	</body>
</html>
